package ali;

import java.awt.image.Kernel;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

/**
 * 15. 三数之和 https://leetcode-cn.com/problems/3sum/submissions/
 *
 * 双指针解法：
 * 首先将数组排序，然后写一层for循环，i从下表0的地方开始，同时定一个下标left在i+1的位置上，定下标right在数组结尾的位置上
 *
 * 然后题目要求在数组中找到 abc 使得a + b +c =0，这里就相当于 让 a = nums[i] b = nums[left] c = nums[right]
 * 如果 nums[i] + nums[left] + nums[right] > 0 说明 此时三数之和大了，因为数组是排序后了，所以right下表就应该向左移动，这样才能让三数之和小一些。
 * 如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。
 * 如果 nums[i] + nums[left] + nums[right] = 0 那就是我们要的结果
 *
 * 参考链接：https://leetcode-cn.com/problems/3sum/solution/15-san-shu-zhi-he-ha-xi-fa-shuang-zhi-zhen-fa-xi-2/
 */
public class Solution_7 {

	public List<List<Integer>> threeSum(int[] nums) {

		if (nums.length < 3) {
			throw new IllegalArgumentException("nums  less than 3");
		}

		//排序
		//[-1,0,1,2,-1,-4]
		//[-4,-1,-1,0,1,2]
		Arrays.sort(nums);

		List<List<Integer>> result = new ArrayList<>();
		// 找出a + b + c = 0
		// 让 a = nums[i], b = nums[left], c = nums[right]
		for (int i = 0; i < nums.length; i++) {

			// 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
			if (nums[i] > 0) {
				return result;
			}

			// 去重：
			if (i > 0 && nums[i] == nums[i-1]) {
				continue;
			}

			int left = i + 1;
			int right = nums.length - 1;
			while (right > left) {
				int count = nums[i] + nums[left] + nums[right];
				if (count > 0) { //说明此时三数之和大了，因为数组是排序后了，所以right下表就应该向左移动，这样才能让三数之和小一些
					right--;
				} else if (count < 0) { //说明此时三数之和小了，left 就向右移动，才能让三数之和大一些
					left++;
				} else {
					result.add(Arrays.asList(nums[i], nums[left], nums[right]));

					// 为避免结果中出现包含重复的三元组，找到一个三元组之后，通过移动左右指针去重
					while (right > left && nums[right] == nums[right - 1]) right--;
					while (right > left && nums[left] == nums[left + 1]) left++;

					// 找到答案时，双指针同时收缩，继续查找
					right--;
					left++;
				}
			}
		}
		return result;
	}

	public static void main(String[] args) {
		Solution_7 solution_7 = new Solution_7();
		solution_7.threeSum(new int[] {-1,0,1,2,-1,-4});
	}

}